package com.leetcode;

import com.leetcode.common.ListNode;

import static com.leetcode.util.LinkedListUtil.createList;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 25. K 个一组翻转链表
 */
public class Solution25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 0 || k == 1) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1, head);
        ListNode cur = head;
        int i = 1;
        ListNode pre = dummyHead;
        ListNode next = null;
        ListNode leftNode = pre.next;
        ListNode rightNode = null;
        while (cur != null) {
            if (i % k == 0) {
                rightNode = cur;
                cur = cur.next;
                next = rightNode.next;
                // 切断链
                rightNode.next = null;

                reverseList(leftNode);

                pre.next = rightNode;
                leftNode.next = next;

                if (i != 1) {
                    pre = leftNode;
                    leftNode = pre.next;
                }
            } else {
                cur = cur.next;
            }
            i++;
        }
        return dummyHead.next;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;

            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
//        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
//        int k = 2;

        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
        int k = 4;

        printList(head);

        ListNode newHead = new Solution25().reverseKGroup(head, k);
        printList(newHead);
    }

}
